package leetcode.day_2021_03_8_2021_03_14;

import java.util.Arrays;

/**
 * 59. 螺旋矩阵 II
 * https://leetcode-cn.com/problems/spiral-matrix-ii/
 */
public class LeetCode0059 {
    public static int[][] generateMatrix(int n) {
        // 记录未填写的格子
        boolean[][] visited = new boolean[n][n];
        // 定义需要填写的矩阵
        int[][] arr = new int[n][n];
        dfs(arr, visited, n, 0, 0, 0);
        return arr;
    }

    public static void dfs(int[][] arr, boolean[][] visited, int n, int i, int j, int num) {
        // 控制填写的条件
        if (i<0 || j<0 || i>=n || j>=n || visited[i][j]) return;
        // 填写数字
        arr[i][j] = ++num;
        visited[i][j] = true;
        // 此处是防止在从下往上填写矩阵 左侧时，出现提前向右转弯填写的情况
        if (j-1<0 || visited[i][j-1]) {
            dfs(arr, visited, n, i-1, j, num);
        }
        // 先从左往右
        dfs(arr, visited, n, i, j+1, num);
        // 再从上往下
        dfs(arr, visited, n, i+1, j, num);
        // 然后从右往左
        dfs(arr, visited, n, i, j-1, num);
        // 最后从下往上
        dfs(arr, visited, n, i-1, j, num);
    }

    public static void main(String[] args) {
        Arrays.stream(generateMatrix(4)).forEach(t -> System.out.println(Arrays.toString(t)));
    }
}
